import java.util.*;

//二叉树遍历：编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
//定义二叉树结点类
class TreeNode1 {
    char val;       //因为树中的值是字符型的
    TreeNode1 left;
    TreeNode1 right;
    TreeNode1(char val){
        this.val = val;
    }
    @Override
    public String toString(){
        return String.format("%c",val);
    }
}
public class Main_KY11 {
    public static void main(String[] args) {
        //自己手动读取输入
        Scanner scanner = new Scanner(System.in);
        //读取一行，读取到String中
        String preorder = scanner.nextLine();
        //利用前序序列，构建二叉树
        //为了方便，把String 转换为 List<character>
        List<Character> preorderList = toList(preorder);
        //构建二叉树
        TreeNode1 root = buildTree(preorderList);
        //要求使用中序遍历，严格按照题目的要求进行输出
        inorderTraversal(root);
    }
    private static List<Character> toList(String s){
        //后边要进行头删，所以 LinkedList 会比 ArrayList 好
        List<Character> list = new LinkedList<>();
        for(char c : s.toCharArray()){
            list.add(c);
        }
        return list;
    }
    public static void inorderTraversal(TreeNode1 root){
        if(root == null){
            return ;
        }
        inorderTraversal(root.left);
        System.out.print(root.val + " ");
        inorderTraversal(root.right);
    }
    public static TreeNode1 buildTree(List<Character> preorder){
        if(preorder.size() == 0){
            return null;
        }
        //头删的方式，取出根的值，删完之后，preorder 中的元素少了一个
        char rootVal = preorder.remove(0);
        if(rootVal == '#'){
            return null;
        }
        TreeNode1 root = new TreeNode1(rootVal);
        //构建左子树，由于 remove(0) 头删，已经删除了一个结点，所以，这里的 preorder 就没有了第一个元素
        root.left = buildTree(preorder);
        //看起来还是 preorder ，但是其实已经少了一个结点
        //注意：在构建左子树的过程中，preorder 中的元素一直在减少，所以还是叫 preorder ，但是其中的元素已经不同了
        //此时 preorder 就剩用来构架右子树的序列了
        root.right = buildTree(preorder);
        return root;
    }
}
